package listbyorder.access101_200.test148;

import listbyorder.utils.ListNode;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/12 10:17
 */
public class Solution1 {

    // 排序链表
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;    // 边界情况
        // 快慢指针将链表分成两个部分
        ListNode c1 = head;
        ListNode c2 = head;
        while (c2.next != null && c2.next.next != null) {
            c1 = c1.next;
            c2 = c2.next.next;
        }
        c2 = c1.next;
        c1.next = null;
        // 分成了两个部分
        ListNode left = sortList(head);
        ListNode right = sortList(c2);
        return merge(left, right);
    }

    // 合并两个链表
    private ListNode merge(ListNode left, ListNode right) {
        if (left == null) return right;
        if (right == null) return left;
        ListNode dummy = new ListNode(-1);
        ListNode temp = dummy;
        while (left != null && right != null) {
            if (left.val < right.val) {
                temp.next = left;
                left = left.next;
            } else {
                temp.next = right;
                right = right.next;
            }
            temp = temp.next;
        }
        while (left != null) {
            temp.next = left;
            left = left.next;
            temp = temp.next;
        }
        while (right != null) {
            temp.next = right;
            right = right.next;
            temp = temp.next;
        }
        return dummy.next;
    }
}
